Efficient Example-Guided Interactive Graph Search

Abstract

We study the problem of interactive graph search (IGS). Given a query entity f, the goal is to identify the target concept in a directed acyclic graph (DAG) concept hierarchy H, which best describes f, through interactions with an oracle. In each interaction, a question in the form of 'Does f belong to concept u?' is asked and the oracle can only answer either YES or NO. The efficiency of an IGS algorithm is measured by the number of questions asked, to identify the target concept, which is referred to as query cost. In theory aspect, we propose the Target-Sensitive IGS (TS-IGS) algorithm that achieves a query cost complexity of O(log n. log/L logn+d·log d n, where L is the length of the pat..